package 题目集.动态规划.最长公共子串;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
 * 字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
 * 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。
 * https://leetcode.cn/problems/distinct-subsequences-ii/description/
 */
public class 不同的子序列II {
    /**
     * 第一思路解：
     *      字符串哈希+dfs。
     *      每个位置都有取或不取的状态，我们可以用dfs来枚举所有的情况。
     *      再用hash来来去重，得到最后的结果。
     *      时间复杂度：O(2^n)
     *      空间复杂度：O(2^n)（用于去重）
     *      空间复杂度爆掉
     * 在思路1中，我们枚举的思路是：让每个位置及其之后自由选择，最后的结果是所有的选择的集合。
     *      我们可以发现，有些位置的结果是之前位置的子集。
     *      例如：aab，a1位置能选择的结果是{a,ab,aa,aab}，a2位置能选择的结果是{a,ab}，a2位置的结果是a1位置的结果的子集。
     *      所以
     */
    char[] chars;
    int n;
    char[] path;
    static int p;
    Set<Long> set=new HashSet<>();


    public int distinctSubseqII(String s) {
        chars=s.toCharArray();
        n=chars.length;
        path=new char[n];
        return dfs(0,0);
    }

    /**
     *
     * @param e:path的最后一个位置
     * @param i：当前可以选择的位置
     * @return
     */
    public int dfs(int e,int i){
        if (i==n) return 0;
        path[e]=chars[i];   //选择当前值
        set.add(hash(e+1));
        int chose = dfs(e + 1, i + 1);
        int noChose=dfs(e,i+1);
        return 0;
    }

    /**
     * 返回path，0到e位置的hash值
     * @param e
     * @return
     */
    public long hash(int e){
        long hash=0;
        for (int i = 0; i < e; i++) {
            hash=hash*p+path[i]-'a';
        }
        return hash;
    }
}
